package com.yanceysong.codetop.s71_s80;

import com.yanceysong.common.TreeNode;


public class S77_Mid_98_验证二叉搜索树 {
    /**
     * .S77_Mid_98_验证二叉搜索树
     * <p>
     * .链接：<a href="https://leetcode.cn/problems/validate-binary-search-tree/">https://leetcode.cn/problems/validate-binary-search-tree/</a>
     * <p>
     * .题目：给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树（BST）。
     * <p>
     * .有效 BST 的定义：
     * .- 节点的左子树只包含 小于 当前节点的数；
     * .- 节点的右子树只包含 大于 当前节点的数；
     * .- 左右子树也必须是二叉搜索树；
     * .- 注意：BST 要求「严格递增」，不允许存在重复值。
     * <p>
     * .核心标签：二叉树 / BST / 递归 / 中序遍历 / 上下界约束
     * <p>
     * .示例：
     * .1) 输入：root = [2,1,3]  输出：true
     * .   ASCII：
     * .       2
     * .      / \\
     * .     1   3
     * .   解释：左 < 根 < 右，满足 BST。
     * <p>
     * .2) 输入：root = [5,1,4,null,null,3,6]  输出：false
     * .   ASCII：
     * .          5
     * .         / \\
     * .        1   4
     * .           / \\
     * .          3   6
     * .   解释：节点 4 的左孩子 3 < 5，却位于根的右子树中，违反「全局约束」。
     * <p>
     * .解题思路（两种经典方案）：
     * .1) 递归 + 上下界约束（推荐）：
     * .   - 从根开始，为每个节点维护它所允许的取值区间 (minAllowed, maxAllowed)；
     * .   - 对左子树更新上界为当前节点值，对右子树更新下界为当前节点值；
     * .   - 若当前节点值不在 (minAllowed, maxAllowed) 内，立刻返回 false；
     * .   - 该方法能自然处理「全局约束」，避免只看父子关系的误判；
     * .   - 为避免 int 溢出，使用 long 作为边界。
     * <p>
     * .2) 中序遍历（迭代/递归）：
     * .   - 对 BST 的中序遍历结果应当「严格递增」；
     * .   - 在遍历过程中记录上一个访问的值 prev，若出现当前值 <= prev，返回 false；
     * .   - 同样可验证严格递增和重复值非法。
     * <p>
     * .复杂度分析：
     * .- 时间复杂度：O(n)，n 为节点数，所有节点各访问一次；
     * .- 空间复杂度：O(h)，h 为树高，递归栈或显式栈的深度；最坏 O(n)，平均 O(log n)。
     * <p>
     * .关键洞察：
     * .- BST 的约束是「全局」的，不仅仅是父子之间；比如某个右子树中的节点也必须 > 根节点；
     * .- 使用上下界在递归路径上传递「祖先约束」，能彻底避免局部判断带来的错误；
     * .- 「严格」二字非常关键：相等视为不合法，因此比较时必须用 < 和 >，不能用 <= 或 >=。
     */
    public boolean isValidBST(TreeNode root) {
        // 使用 long 作为边界，避免节点值为 Integer.MIN_VALUE/Integer.MAX_VALUE 时溢出
        return isValidBSTWithinBounds(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /**
     * .递归辅助：当前节点必须严格位于 (minAllowed, maxAllowed) 区间内。
     * <p>
     * .@param current    当前节点
     * .@param minAllowed 当前路径允许的最小下界（开区间）
     * .@param maxAllowed 当前路径允许的最大上界（开区间）
     * .@return 当前子树是否满足 BST 定义
     */
    private boolean isValidBSTWithinBounds(TreeNode current, long minAllowed, long maxAllowed) {
        // 空节点视为合法 BST（递归基）
        if (current == null) {
            return true;
        }
        // 当前值必须严格在开区间 (minAllowed, maxAllowed) 内；相等不合法
        if (current.val <= minAllowed || current.val >= maxAllowed) {
            return false;
        }
        // 左子树：上界收缩为当前值；右子树：下界扩张为当前值
        return isValidBSTWithinBounds(current.left, minAllowed, current.val)
               && isValidBSTWithinBounds(current.right, current.val, maxAllowed);
    }

    /*
     * .可选方案：中序遍历校验严格递增（留作参考）。
     * .若需要演示另一种方式，可取消注释并配合 main 方法测试。
     */
    // private boolean isValidBSTInorder(TreeNode root) {
    //     Long prev = null; // 记录上一个访问的值
    //     java.util.Deque<TreeNode> stack = new java.util.ArrayDeque<>();
    //     TreeNode cur = root;
    //     while (cur != null || !stack.isEmpty()) {
    //         while (cur != null) {
    //             stack.push(cur);
    //             cur = cur.left;
    //         }
    //         cur = stack.pop();
    //         if (prev != null && cur.val <= prev) {
    //             return false; // 不严格递增，非法
    //         }
    //         prev = (long) cur.val;
    //         cur = cur.right;
    //     }
    //     return true;
    // }

    /**
     * .示例与测试：覆盖典型与边界场景。
     * .说明：main 中使用简单的构造，配合 ASCII 图解与期望值校验。
     */
    public static void main(String[] args) {
        S77_Mid_98_验证二叉搜索树 solver = new S77_Mid_98_验证二叉搜索树();
        System.out.println("=== 验证二叉搜索树测试开始 ===");

        // 测试1：标准合法 BST [2,1,3]
        System.out.println("\n--- 测试1：合法 BST [2,1,3] ---");
        TreeNode t1 = new TreeNode(2);
        t1.left = new TreeNode(1);
        t1.right = new TreeNode(3);
        System.out.println("结构：\n  2\n / \\\n1   3");
        boolean r1 = solver.isValidBST(t1);
        System.out.println("结果：" + r1 + " (期望：true)");
        assert r1;

        // 测试2：经典非法案例 [5,1,4,null,null,3,6]
        System.out.println("\n--- 测试2：非法 BST [5,1,4,null,null,3,6] ---");
        TreeNode t2 = new TreeNode(5);
        t2.left = new TreeNode(1);
        t2.right = new TreeNode(4);
        t2.right.left = new TreeNode(3);
        t2.right.right = new TreeNode(6);
        System.out.println("结构：\n    5\n   / \\\n  1   4\n     / \\\n    3   6");
        boolean r2 = solver.isValidBST(t2);
        System.out.println("结果：" + r2 + " (期望：false)");
        assert !r2;

        // 测试3：左子树直接违反 [5,6,7]
        System.out.println("\n--- 测试3：左子树直接违反 [5,6,7] ---");
        TreeNode t3 = new TreeNode(5);
        t3.left = new TreeNode(6); // 左子应当 < 5，这里为 6，非法
        t3.right = new TreeNode(7);
        System.out.println("结构：\n  5\n / \\\n6   7");
        boolean r3 = solver.isValidBST(t3);
        System.out.println("结果：" + r3 + " (期望：false)");
        assert !r3;

        // 测试4：深层全局约束违反（右子树里出现比根小的值）
        System.out.println("\n--- 测试4：右子树出现比根小的值 ---");
        TreeNode t4 = new TreeNode(5);
        t4.left = new TreeNode(1);
        t4.right = new TreeNode(7);
        t4.right.left = new TreeNode(4); // 右子树中的 4 < 根 5，非法
        System.out.println("结构：\n   5\n  / \\\n 1   7\n    /\n   4");
        boolean r4 = solver.isValidBST(t4);
        System.out.println("结果：" + r4 + " (期望：false)");
        assert !r4;

        // 测试5：重复值（严格递增不允许重复）
        System.out.println("\n--- 测试5：重复值 ---");
        TreeNode t5 = new TreeNode(2);
        t5.left = new TreeNode(2); // 左子等于根，非法（应严格 <）
        System.out.println("结构：\n  2\n /\n2");
        boolean r5 = solver.isValidBST(t5);
        System.out.println("结果：" + r5 + " (期望：false)");
        assert !r5;

        // 测试6：空树（视为合法 BST）
        System.out.println("\n--- 测试6：空树 ---");
        TreeNode t6 = null;
        boolean r6 = solver.isValidBST(t6);
        System.out.println("结果：" + r6 + " (期望：true)");
        assert r6;

        // 测试7：单节点
        System.out.println("\n--- 测试7：单节点 ---");
        TreeNode t7 = new TreeNode(42);
        boolean r7 = solver.isValidBST(t7);
        System.out.println("结果：" + r7 + " (期望：true)");
        assert r7;

        // 测试8：极值边界（使用 long 边界避免溢出问题）
        System.out.println("\n--- 测试8：极值边界 ---");
        TreeNode t8 = new TreeNode(Integer.MIN_VALUE);
        t8.right = new TreeNode(Integer.MAX_VALUE);
        boolean r8 = solver.isValidBST(t8);
        System.out.println("结果：" + r8 + " (期望：true)");
        assert r8;

        // 测试9：不平衡但合法的右斜树
        System.out.println("\n--- 测试9：右斜合法树 ---");
        TreeNode t9 = new TreeNode(1);
        t9.right = new TreeNode(2);
        t9.right.right = new TreeNode(3);
        t9.right.right.right = new TreeNode(4);
        boolean r9 = solver.isValidBST(t9);
        System.out.println("结果：" + r9 + " (期望：true)");
        assert r9;

        // 测试10：左斜非法树（递减链）
        System.out.println("\n--- 测试10：左斜非法树（递减链） ---");
        TreeNode t10 = new TreeNode(4);
        t10.left = new TreeNode(3);
        t10.left.left = new TreeNode(2);
        t10.left.left.left = new TreeNode(1);
        // 注意：纯左斜并不必然非法，这里为了制造非法，在左链中插入一个等于父的节点
        t10.left.val = 4; // 让第二层等于根，形成重复，非法
        boolean r10 = solver.isValidBST(t10);
        System.out.println("结果：" + r10 + " (期望：false)");
        assert !r10;

        System.out.println("\n=== 所有测试完成 ===");
    }
}
